package com.guojialin.learning;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 数据结构与算法-菜鸟教程：
 * https://www.runoob.com/data-structures/insertion-sort.html
 * <p>
 * https://zhuanlan.zhihu.com/p/42541704
 * 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
 * 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
 */
public class SortAlgs {

    public SortAlgs(int length, int maxNum) {
        this.arr = new int[length];
        for (int i = 0; i < length; i++) {
            this.arr[i] = (int) (Math.random() * maxNum);
        }
    }

    protected int[] arr = null; // new int[]{4, 5, 6, 1, 9, 23, 45, 67, 43, 73, 7, 34, 86, 54, 65, 89, 34, 86, 54, 65, 89};

    /**
     * Bubble
     * 两两比较交换，每次可以把最大(小)值移动到数组末尾
     * 每一趟比较都比上一次少比较一个值
     * O(n^2)
     */
    public void bubbleSort(int[] arr) {

        if (arr == null || arr.length == 0) {
            return;
        }
        long time = System.nanoTime();
        int i = 0;
        int j = 0;
        long len = arr.length;
        long step = 0;
        long move = 0;
        for (i = 0; i < len - 1; i++) {
            for (j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    move++;
                }
                step++;
            }
        }
        System.out.println("bubble sort:" + (System.nanoTime() - time) / 1000000d + "ms");
        System.out.println("step:" + step);
        System.out.println("move:" + move);
    }

    /**
     * Selection
     * O(n^2)
     *
     * @param arr
     */
    public void selectionSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        long time = System.nanoTime();
        long len = arr.length;
        long step = 0;
        long move = 0;
        for (int i = 0; i < len; i++) {
            int minKey = arr[i];
            for (int j = i; j < len; j++) {
                if (minKey > arr[j]) {
                    int temp = arr[j];
                    arr[j] = minKey;
                    minKey = temp;
                    move++;
                }
                step++;
            }
            arr[i] = minKey;
        }
        System.out.println("selection sort:" + (System.nanoTime() - time) / 1000000d + "ms");
        System.out.println("step:" + step);
        System.out.println("move:" + move);
    }

    long time = 0;
    long step = 0;
    long move = 0;

    /**
     * QSort
     * O(nlog(2)n)
     *
     * @param arr
     */
    public void quickSort(int[] arr, int left, int right) {
        if (arr == null || arr.length == 0) {
            return;
        }

        if (time == 0) {
            time = System.nanoTime();
            step = 0;
            move = 0;
        }

        if (left > right) {
            return;
        }
        int i, j, temp;
        temp = arr[left];
        i = left;
        j = right;

        while (i != j) {
            // 从右边找
            while (arr[j] >= temp && i < j) {
                j--;
//                step++;
            }
            // 再从左边找
            while (arr[i] <= temp && i < j) {
                i++;
//                step++;
            }
            if (i < j) {
                swap(arr, i, j);
//                move++;
            }
        }

        arr[left] = arr[i];
        arr[i] = temp;
        // 左边递归
        quickSort(arr, left, i - 1);
        // 右边递归
        quickSort(arr, i + 1, right);
    }

    /**
     * 插入排序
     * O(n2)
     *
     * @param arr
     */
    public void insertionSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        long time = System.nanoTime();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
        System.out.println("insertion sort:" + (System.nanoTime() - time) / 1000000d + "ms");
    }

    /**
     * 计数排序
     * 10w数字排序，时间是优秀的
     * arr length:100000
     * insertion sort:7117.187403ms
     * counting sort:4.357967ms
     * qsort:23.477901ms
     * asort:25.19518ms
     * 空间换时间
     */
    public int[] countingSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr;
        }
        long time = System.nanoTime();
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int num : arr) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }

        int count[] = new int[max - min + 1];

        for (int num : arr) {
            count[num - min]++;
        }
        int[] result = new int[arr.length];
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                result[index++] = min + i;
                count[i]--;
            }
        }
        System.out.println("counting sort:" + (System.nanoTime() - time) / 1000000d + "ms");
        return result;
    }

    /**
     * 桶排序
     * 十万数字排序时间
     * <p>
     * arr length:100000
     * insertion sort:7756.931291ms
     * counting sort:4.814607ms
     * bucket sort:44.073116ms
     * qsort:18.380333ms
     * asort:27.570386ms
     *
     * @param arr
     */
    public void bucketSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        long time = System.nanoTime();
        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        // 将每个元素放入桶
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
        System.out.println("bucket sort:" + (System.nanoTime() - time) / 1000000d + "ms");
    }


    public void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }


    /**
     * arr length:1000000
     * ==
     * bubble sort:1,944,966.508282ms
     * step:499,999,500,000
     * move:249,832,085,137
     * -------------------------
     * selection sort:1,969,407.395351ms
     * step:500,000,500,000
     * move:183,886,867,291
     * -------------------------
     * qsort:143.313799ms
     * step:25,859,244
     * move:3,918,195
     * -------------------------
     * 双轴快排
     * 该算法在许多数据集上提供了O(nlog(N))性能，导致其他的快速性能下降到二次性能，并且通常比传统的(单枢轴)快速排序实现更快。
     * https://zhuanlan.zhihu.com/p/374041792
     * 图解双轴快排：
     * https://www.cnblogs.com/bigsai/p/13930945.html
     * dpqsort:100.519209ms
     * <p>
     * 1亿数字排序对比
     * =======
     * arr length:100000000
     * qsort:15,540.287168ms
     * dpqsort:10,357.905176ms
     *
     * @param args
     */
    public static void main(String[] args) {
        int count = 100000;
        SortAlgs algs = new SortAlgs(count, count);
        System.out.println("arr length:" + algs.arr.length);

//        int[] bArr = algs.arr.clone();
//        algs.bubbleSort(bArr);
//
//        int[] sArr = algs.arr.clone();
//        algs.selectionSort(sArr);

        int[] iArr = algs.arr.clone();
        algs.insertionSort(iArr);

        int[] cArr = algs.arr.clone();
        algs.countingSort(cArr);

        int[] bArr = algs.arr.clone();
        algs.bucketSort(bArr);

        int[] qArr = algs.arr.clone();
        algs.quickSort(qArr, 0, algs.arr.length - 1);
        System.out.println("qsort:" + (System.nanoTime() - algs.time) / 1000000d + "ms");
//        System.out.println("step:" + algs.step);
//        System.out.println("move:" + algs.move);


        /**
         * DualPivotQuicksort - 双轴快速排序
         *
         * 我提到了在使用Arrays.sort()时针对int[]会使用DualPivotQuicksort类进行排序。
         * 实际上针对非对象类型，都会使用这个方法。比传统快排更快。
         * 分治思想。"divide and conquer"
         * 使用两个轴pivot而不是一个。
         *
         * JDK 1.8中DualPivotQuicksort并【没有完全使用双轴快速排序】的做法，
         * 而是按照【基本数据类型】和【数组长度】，
         * 用了【快速排序】、【计数排序】、【归并排序】
         *
         * 对于排序算法来说，最耗时的部分一般来说为两种：【比较】和【交换】。当然这也是排序算法的核心步骤。
         *
         */
        int[] aArr = algs.arr.clone();
        long t = System.nanoTime();
        Arrays.sort(aArr);
        System.out.println("asort:" + (System.nanoTime() - t) / 1000000d + "ms");
    }

    @Override
    public String toString() {
        return "SortAlgs{" +
                "arr=" + Arrays.toString(arr) +
                '}';
    }

}